#if !defined(DISJOINT_SET_H)
#define DISJOINT_SET_H

#include <deque>
#include <vector>
#include <utility>
#include <list>
#include <algorithm>
namespace disjoint_set_private
{



//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
//
//	t_cluster_id
//
// 			cluster of IDs
//			belongs to a super-cluster (see below)
//
struct t_super_cluster;
struct t_cluster_id
{

	std::list<unsigned> 		ids;
	t_super_cluster* 	supercluster;

	void push_back(unsigned id)	{	ids.push_back(id);	}
	t_cluster_id(t_super_cluster* supercluster_)
		:supercluster(supercluster_){}
};


typedef t_cluster_id* p_cluster_id;

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
//
//	t_super_cluster
//
//
// 			when merging large (> LIMIT) clusters, just put them in a
//			super_cluster instead of
//			going through each cluster and repointing members
//

struct t_super_cluster
{
	typedef std::list<p_cluster_id>::iterator iter;


	// position in parent for memory handling
	unsigned				index;

	// number of IDs in all child clusters
	unsigned 				total_size;

	// point to the lookup table for IDs to clusters for merging clusters
	std::deque<p_cluster_id>*	id_to_p_cluster;

	// list of child clusters which point to me
	std::list<p_cluster_id>		clusters;

	// list of clusters which are probably smaller than LIMIT
	// 	(clusters not here are definitely larger and will not be merged)
	std::list<p_cluster_id>		small_clusters;


	//
	//	constructor
	//
	t_super_cluster(unsigned index_, std::deque<p_cluster_id>& id_to_p_cluster_):
				index(index_),
				total_size(0),
				id_to_p_cluster(&id_to_p_cluster_){}

	//
	//	destructor frees member clusters
	//
	~t_super_cluster();

	//
	//	add new child cluster
	//
	p_cluster_id		add_new_cluster(unsigned id1, unsigned id2);


	//
	//	swallow other's clusters
	//
	t_super_cluster& engulf(t_super_cluster& other);

	//
	//	merge constituent clusters if small
	//
	void compress();
};

void output_sorted_clusters(std::deque<t_super_cluster>&				super_clusters,
							std::deque<std::vector<unsigned> >&	output_clusters);

t_super_cluster& get_new_supercluster(	std::deque<t_super_cluster>&	super_clusters,
										std::deque<unsigned>&		free_super_clusters,
										std::deque<p_cluster_id>&	id_to_p_cluster);
void free_supercluster(     t_super_cluster& cluster,
							std::deque<unsigned>& free_super_clusters);


}

//________________________________________________________________________________________

//	disjoint_set_clusters

//________________________________________________________________________________________
template <typename PROGRESS_COUNTER, typename ITER>
void disjoint_set_clusters(ITER  									pairs_iter,
							 ITER  									pairs_end,
							 std::deque<std::vector<unsigned> >&	output_clusters,
							 PROGRESS_COUNTER& 						dots)
{
	std::deque<disjoint_set_private::t_super_cluster>	super_clusters;
	std::deque<unsigned>								free_super_clusters;

	// lookup cluster from ID
	std::deque<disjoint_set_private::p_cluster_id>	id_to_p_cluster;

	while (pairs_iter != pairs_end)
	{
		++dots;
		unsigned id1 = pairs_iter->first;
		unsigned id2 = pairs_iter->second;
		++pairs_iter;

		// ignore self-self pairs
		if (id1 == id2)
			continue;

		//
		// expand size of id_to_p_cluster if necessary
		//
		unsigned max_id = std::max(id1, id2);
		if (max_id >= id_to_p_cluster.size())
			id_to_p_cluster.insert(	id_to_p_cluster.end(),
									max_id - id_to_p_cluster.size() + 1, 0);


		// get clusters of both
		disjoint_set_private::p_cluster_id& curr_cluster1 = id_to_p_cluster[id1];
		disjoint_set_private::p_cluster_id& curr_cluster2 = id_to_p_cluster[id2];

		//
		// 1. add new cluster if neither is yet clustered
		//
		if (curr_cluster1 == 0 && curr_cluster2 == 0)
			// these two ids make up a new cluster inside a new super cluster
			curr_cluster1 =
			curr_cluster2 =	disjoint_set_private::get_new_supercluster(super_clusters,
												 free_super_clusters,
												 id_to_p_cluster).add_new_cluster(id1, id2);




		//
		// 2. Link cluster 2 to cluster 1 if both already clustered
		//
		else if (curr_cluster1 && curr_cluster2)
		{

			// ignore if both already part of the same cluster
			if (curr_cluster1->supercluster == curr_cluster2->supercluster)
				continue;
			disjoint_set_private::free_supercluster(
											curr_cluster1->supercluster
											->engulf(	*curr_cluster2->supercluster),
														free_super_clusters);

		}


		//
		// 3. add id 2 to cluster 1 if id 2 is unclustered
		//
		else if (curr_cluster1)
		{
			curr_cluster2 = curr_cluster1;
			id_to_p_cluster[id1]->push_back(id2);
			id_to_p_cluster[id1]->supercluster->total_size++;

		}



		//
		// 4. add id 1 to cluster 2 if id 1 is unclustered
		//
		else
		{
			curr_cluster1 = curr_cluster2;
			id_to_p_cluster[id2]->push_back(id1);
			id_to_p_cluster[id2]->supercluster->total_size++;
		}
	}
	output_sorted_clusters(super_clusters, output_clusters);

}

template <typename T>
inline void disjoint_set_clusters(const std::deque<T>&				pairs,
									std::deque<std::vector<unsigned> >&	output_clusters)
{
	unsigned dots;
	disjoint_set_clusters(pairs.begin(), pairs.end(), output_clusters, dots);
}


template <typename progress_counter, typename ITER>
inline void disjoint_set_clusters(	ITER		pairs_iter,
										ITER		pairs_end,
										std::deque<std::vector<unsigned> >&	output_clusters)
{
	unsigned dots;
	return disjoint_set_clusters(pairs_iter, pairs_end, output_clusters, dots);
}

template <typename T, typename progress_counter>
inline void disjoint_set_clusters(	const std::deque<T>&				pairs,
										std::deque<std::vector<unsigned> >&	output_clusters,
										progress_counter& 					dots)
{
	disjoint_set_clusters(pairs.begin(), pairs.end(), output_clusters, dots);
}


#endif
